package DP算法编程_01;

/**
 * User: Mazexal
 * Date: 2021/2/9
 */
public class DpNormal {
    // 使用记忆数组解决硬币问题

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1,2,5}, 11));
    }

    public static int coinChange(int[] A, int M) {
        int n = A.length;
        // 这里的长度为 M+1, 因为有0
        int[] f = new int[M + 1];
        int i, j;
        f[0] = 0;
        for (i = 1; i <= M; i++) {
            f[i] = Integer.MAX_VALUE;
            // select last coin
            for (j = 0; j < n; j++) {
                if (i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE && f[i - A[j]] + 1 < f[i]) {
                    f[i] = f[i - A[j]] + 1;
                }
            }
        }
        // 边界情况, 无解
        if (f[M] == Integer.MAX_VALUE) {
            return -1;
        } else {
            return f[M];
        }
    }


}
